#include <iostream>
#include <algorithm>
using namespace std;
const int MINS = -(1 << 30);
int cut_rod(int p[],int n)
{
	if (n == 0)
		return 0;
	int q = MINS;
	for(int i=1;i<=n;++i)
	{
		q = max(q, p[i] + cut_rod(p, n - i));
	}
	return q;
}

int bottom_up_cut_rod(int p[],int n)
{
	int *r = new int[n + 1];
	r[0] = 0;
	for(int j=1;j<=n;++j)
	{
		int q = MINS;
		for(int i=1;i<=j;++i)
		{
			q = max(q, p[i] + r[j - i]);
		}
		r[j] = q;
	}
	for(int i=1;i<=n;++i)
	{
		if(i!=1)
			cout << " ";
		cout << r[i];
	}
	cout << endl;
	int t = r[n];
	delete[]r;
	return t;
}

int main()
{
	int p[] = { 0,1,5,8,9,10,17,17,20,24,30 };
	cout << bottom_up_cut_rod(p, 10)<<endl;
	
}